Pada 7 Jun 1958, semasa pertandingan Ketua Pemuda UMNO, beliau dikalahkan oleh Sardon Jubir yang menjadi Menteri Kerjaraya, Pos dan Telekomunikasi. Sardon terpilih semula semula sebagai Ketua Pemuda UMNO dengan 44 undi dan Sulaiman 13 undi. [4]Beliau adalah veteran UMNO. Satu masa, Tunku Abdul Rahman, Dato' Abdul Razak Hussein, Haji Ahmad Maliki, Haji Sulaiman Palestin dan beberapa pemimpin lain telah bertemu dengan Sheikh Abdullah Fahim untuk mendapatkan bimbingan ,nasihat dan penentuan tarikh kemerdekaan yang sesuai untuk Tanah Melayu.[5] Selaku wakil Pemuda UMNO dari Nibong Tebal, Haji Sulaiman Palestin pernah menegaskan bahawa "kami akan mendapatkan kemerdekaan sama ada Sultan sultan mahukannya ataupun tidak".[6]

Akhir hayatnya beliau menyertai Parti Melayu Semangat 46 dan menjadi Ahli Majlis Tertinggi Semangat 46. [7] Akhbar Watan Bil: 341 26 Julai 1988 melaporkan Sulaiman Palestin berkata beliau tidak akan menghalalkan bahagiannya dalam harta UMNO lama sekiranya harta itu diambil oleh UMNO Baru walaupun undang-undang menghalalkannya.[8]